C语言迪杰斯特拉算法求最短路径详解 |
您所在的位置：网站首页 › c语言为什么printf 不工作 › C语言迪杰斯特拉算法求最短路径详解 |
C语言迪杰斯特拉算法求最短路径详解
|
准备一张地图
盗取了一个不知名朋友的图，嘻嘻。 目的：在一张地图中找出地点A和地点B的一条最短路径（实际上该算法每次运算会求出地点A到其他各个地点的各一条最短路径）。 过程： 1）以从1号地点到4号地点为例。 2）标记1号地点。（标记的作用将在后面得到体会，当全部地点都被标记完时，最短路径就求出来了！），此时在草稿本上画出（99为不可直达） 线路 距离总和 1->2 2 1->3 5 1->4 99 1->5 99 1->6 99 1->7 993）通过比较我们可以得到1->2这段距离是最短的，那么此时我们标记2号地点表示已经找到了1号到2号的最短距离。那么这时候我们从1号到2号以外地点的距离是否能减短，比较1->3和1–>2->3可知1->2->3距离为4，更短一些，修改1号到3号的线路和距离，再依次比较剩下未标记的地点线路。然后修改草稿 线路 距离总和 1->2 2 1->2->3 4 1->2->4 6 1->2->5 8 1->6 99 1->7 994）通过比较我们可以得到未标记的地点中1到3号的距离最短，可知1到3号的最短路径也已经得出结论。那么标记3号，此时1号到未标记的地点的距离是原来的路线近一些呢，还是先去3号，在从3号去更近呢，比较一下。拿4号为例，上一次结论中1->2->4=6，此时1->2->3->4=5,更短一些，修改该路线；然后依次比较1到5号，1到6号，1到7号的最短距离并修改可以更短的。 线路 距离总和 1->2 2 1->2->3 4 1->2->3->4 5 1->2->5 8 1->2->3->6 7 1->7 995）根据以上规律此时标记4号，比较并修改可以得到更短距离的5、6、7号地点 线路 距离总和 1->2 2 1->2->3 4 1->2->3->4 5 1->2->5 8 1->2->3->4->6 6 1->2->3->4->7 96）根据以上规律此时标记6号，比较并修改可以得到更短距离的5、7号地点 线路 距离总和 1->2 2 1->2->3 4 1->2->3->4 5 1->2->5 8 1->2->3->4->6 6 1->2->3->4->6->7 87）根据以上规律此时标记5号（两距离一样，随意选一个），比较并修改可以得到更短距离的7号地点 线路 距离总和 1->2 2 1->2->3 4 1->2->3->4 5 1->2->5 8 1->2->3->4->6 6 1->2->3->4->6->7 88）标记7号地点，此时已经没有未标记的地点，表示所有地点均已经找到了从1号到它的最短路径！算法结束。 算法总结求A到B的最短路径 1、在地点集合Map中，先标记A。 2、存储A直接到其他各地点的路径和距离，选择最短的一条，假设为A->C，那此时标记C，表示已经找到A到C的最短路径，比较一下A->其他的距离和A->C->其他的距离，如果经过C的路线比较短，修改A->其他为A->C->其他，并及时更新其目前最短距离。 3、重复执行第2步直到所有地点均被标记。 4、输出结果中的A->…->B路径和距离（…表示0到多个中间点）。 代码实现用一个地图结构保存该地图 //最大地点数 #define MAXCOUNT 20 //不可能距离值（两地点无直接线路时） #define MAXDISTANCE 99 //地图结构 typedef struct map { //地点数量 int nodeCount; //地点标识 int id[MAXCOUNT]; //各地点间距离 distance[i][j]=distance[j][i]，表示i地点和j地点的距离 int distance[MAXCOUNT][MAXCOUNT]; }Map;由于该地图线路较多，这里采用文件读入方式，编写map.txt，格式为 地点数n1 线路数n2 n2个（地点a的id 地点b的id a到b的距离 ） 7 12 1 2 2 1 3 5 2 3 2 2 5 6 2 4 4 4 3 1 3 6 3 4 5 4 4 6 1 4 7 4 5 7 1 6 7 2编写文件读入地图函数 //读取map.txt中的信息 void readMap(Map *map) { //以读形式打开文件 FILE *fp=fopen("map.txt","r"); //读取地点数量 fscanf(fp,"%d",&map->nodeCount); int n; //读取路线数量 fscanf(fp,"%d",&n); int i,j; //初始化地点id for(i=1;inodeCount;i++) { map->id[i]=i; } //初始化每两地点均无路线 for(i=1;i map->distance[i][j]=MAXDISTANCE; } } //读入线路 int k,d; for(k=1;k int i,j; printf("地点个数:%d\n",map.nodeCount); printf("各地点间距离（...表示无路线）:\n"); printf(" "); for(i=1;i printf("%-3d ",i); for(j=i;j printf("... "); } else { printf("%-3d ",map.distance[i][j]); } } printf("\n"); } printf("\n"); }编写路径结构 //路线结构 typedef struct road { //经过地点id int path[MAXCOUNT]; //距离 int minDistance; //经过的地点数 int count; }Road;迪杰斯特拉算法实现求地点a到其他地点的最短路径 //迪杰斯特拉算法求地点a到其他地点的最短路径 Road *djstl(Map map,int id_a) { //所有路线 Road r[MAXCOUNT]; //标记数组（0为未标记，1为已标记） int flag[MAXCOUNT]={0}; int i; //初始化所有路线 for(i=1;i //寻找a到未标记的地点的最短路线的下标 int index=-1; for(i=1;i if(index==-1) { index=i; } else if(r[i].minDistance return r; } //标记index flag[index]=1; //比较并修改其他路线此时的最短路径 for(i=1;i //a->...->i短还是a->...->index->i短，后者短，则说明a到i有更好的选择 if(r[i].minDistance>r[index].minDistance+map.distance[index][i]) { /*将r[index]的值赋予r[i]，并修改r[i]的最短路径*/ r[i].count=r[index].count+1; int j; for(j=0;j printf("距离:%d\n",rab.minDistance); int i; printf("路线:"); for(i=0;i",rab.path[i]); } printf("%d\n\n",rab.path[i]); }编写主函数测试 int main() { //地图变量 Map map; //读取地图 readMap(&map); //打印地图信息 displayMap(map); int id_a,id_b; printf("id_a:"); scanf("%d",&id_a); printf("id_b:"); scanf("%d",&id_b); printf("搜索最短路径中，请稍后...\n"); Road *r=djstl(map,id_a); printf("搜索最短路径完毕！\n"); displayRoad(r[id_b]); return 0; }测试1号到4号地点的最短路径 |
测试1到7号地点的最短距离 
结果和以上所算一致，实现完毕！【本文地址】
今日新闻 |
推荐新闻 |